<!DOCTYPE html>
<html>
  <head>
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0" name="viewport">
  <meta name="description" content="tong.li&#39;s blog">
  <meta name="keyword" content="彤哥哥博客，95后技术爱好者,现就职于同程旅行/同程艺龙上海分公司，专注于互联网技术分享的平台。">
  
    <link rel="shortcut icon" href="/css/images/icon.png">
  
  <title>
    
      【数据结构与算法】不知所措的二分查找 | 彤哥哥的博客
    
  </title>
  <link href="https://cdn.staticfile.org/font-awesome/4.7.0/css/font-awesome.min.css" rel="stylesheet">
  <link href="https://cdn.staticfile.org/nprogress/0.2.0/nprogress.min.css" rel="stylesheet">
  <link href="https://cdn.staticfile.org/highlight.js/9.12.0/styles/tomorrow-night.min.css" rel="stylesheet">
  
<link rel="stylesheet" href="/css/style.css">

  
  <script src="https://cdn.staticfile.org/jquery/3.2.1/jquery.min.js"></script>
  <script src="https://cdn.staticfile.org/geopattern/1.2.3/js/geopattern.min.js"></script>
  <script src="https://cdn.staticfile.org/nprogress/0.2.0/nprogress.min.js"></script>
  
    
<script src="/js/qrious.js"></script>

  
  
  
  
    <!-- MathJax support START -->
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="https://cdn.staticfile.org/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
    <!-- MathJax support END -->
  


  
  
    
<script src="/js/local-search.js"></script>


<meta name="generator" content="Hexo 5.4.2"></head>
<div class="wechat-share">
  <img src="/css/images/logo.png" />
</div>
  <body>
    <header class="header fixed-header">
  <div class="header-container">
    <a class="home-link" href="/">
      <div class="logo"></div>
      <span>彤哥哥的博客</span>
    </a>
    <ul class="right-list">
      
        <li class="list-item">
          
            <a href="/" class="item-link">主页</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/series/" class="item-link">分类</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/tags/" class="item-link">标签</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/archives/" class="item-link">归档</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/project/" class="item-link">项目</a>
          
        </li>
      
        <li class="list-item">
          
            <a href="/about/" class="item-link">关于</a>
          
        </li>
      
      
        <li class="menu-item menu-item-search right-list">
    <a role="button" class="popup-trigger">
        <i class="fa fa-search fa-fw"></i>
    </a>
</li>
      
    </ul>
    <div class="menu">
      <span class="icon-bar"></span>
      <span class="icon-bar"></span>
      <span class="icon-bar"></span>
    </div>
    <div class="menu-mask">
      <ul class="menu-list">
        
          <li class="menu-item">
            
              <a href="/" class="menu-link">主页</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/series/" class="menu-link">分类</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/tags/" class="menu-link">标签</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/archives/" class="menu-link">归档</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/project/" class="menu-link">项目</a>
            
          </li>
        
          <li class="menu-item">
            
              <a href="/about/" class="menu-link">关于</a>
            
          </li>
        
      </ul>
    </div>
    
      <div class="search-pop-overlay">
    <div class="popup search-popup">
        <div class="search-header">
            <span class="search-icon">
                <i class="fa fa-search"></i>
            </span>
            <div class="search-input-container">
                <input autocomplete="off" autocapitalize="off"
                    placeholder="Please enter your keyword(s) to search." spellcheck="false"
                    type="search" class="search-input">
            </div>
            <span class="popup-btn-close">
                <i class="fa fa-times-circle"></i>
            </span>
        </div>
        <div id="search-result">
            <div id="no-result">
                <i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
            </div>
        </div>
    </div>
</div>
    
  </div>
</header>

    <div id="article-banner">
  <h2>【数据结构与算法】不知所措的二分查找</h2>
  <p class="post-date">2022-01-23</p>
  <div class="arrow-down">
    <a href="javascript:;"></a>
  </div>
</div>
<main class="app-body flex-box">
  <!-- Article START -->
  <article class="post-article">
    <section class="markdown-content"><h1 id="1-前言"><a href="#1-前言" class="headerlink" title="1.前言"></a>1.前言</h1><p>大家好，现在是22年1月23日晚8点35分，此时夜色朦胧，弯月如钩。</p>
<p>晚上酒过三巡，菜过五味，我随口问了小伙伴A一个问题：二分查找算法会写吗？</p>
<p>小伙伴A搞笑的答道：这都不会，还写什么代码，干脆回家抱孩子得了。</p>
<p>当时，惹得众人哈哈大笑。于是我们开启长达1个小时的二分查找之论。</p>
<h1 id="2-不入眼的二分查找"><a href="#2-不入眼的二分查找" class="headerlink" title="2. 不入眼的二分查找"></a>2. 不入眼的二分查找</h1><p>二分查找法，生活中随处可以见。</p>
<p>我们现在来做一个猜字游戏。以下是游戏规则：</p>
<blockquote>
<p>我随机写一个0到99之间的数字，然后你来猜我写的是什么。</p>
<p>猜的过程中，你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。</p>
<p>你来想想，如何快速猜中我写的数字呢？</p>
</blockquote>
<p>假设我写的数字是23，你可以按照下面的步骤来试一试。（如果猜测范围的数字有偶数个，中间数有两个，就选择较小的那个。）</p>
<p><img src="https://ltyeamin.github.io/imgs/2022/03/20220312171718.png"></p>
<p>7次就猜出来了，是不是很快？这个例子用的就是二分思想，按照这个思想，即便我让你猜的是0到999的数字，最多也只要10次就能猜中。不信的话，你可以试一试。</p>
<p>玩了上面游戏后，那么今天我们讲一种针对有序数据集合的查找算法，二分查找（Binary Search）算法，也叫折半查找算法。</p>
<p>我们大学数据结构与算法课程都学过二分算法，思想其实非常简单，很多小伙伴很容易就能理解，但是看似越简单的东西往往越难掌握好，想要灵活应用就更加困难。</p>
<p>说到二分查找，我们有两个大的前提：</p>
<ol>
<li>必须是顺序存储，简单来说就是数组存储。</li>
<li>元素必须有序，简单来说就是已经排序过了。</li>
</ol>
<p><img src="https://ltyeamin.github.io/imgs/2022/03/20220312171422.png"></p>
<p>相信大家直接可以写出如下代码：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">  * 简单的二分查找</span></span><br><span class="line"><span class="comment">  * <span class="doctag">@param</span> arr    查找数组</span></span><br><span class="line"><span class="comment">  * <span class="doctag">@param</span> target 查找指定的值</span></span><br><span class="line"><span class="comment">  * <span class="doctag">@return</span>       返回查找值的数组索引，返回-1表示查询无结果</span></span><br><span class="line"><span class="comment">  */</span></span><br><span class="line"> <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">simpleBinarySearch</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> target)</span> &#123;</span><br><span class="line">     <span class="comment">// 获取数组长度</span></span><br><span class="line">     <span class="type">int</span> <span class="variable">len</span> <span class="operator">=</span> arr.length;</span><br><span class="line">     <span class="comment">// 校验数组</span></span><br><span class="line">     <span class="keyword">if</span> (arr == <span class="literal">null</span> ||  len == <span class="number">0</span>) &#123;</span><br><span class="line">         <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">     &#125;</span><br><span class="line">     <span class="comment">// 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引</span></span><br><span class="line">     <span class="type">int</span> <span class="variable">low</span> <span class="operator">=</span> <span class="number">0</span>, high = len - <span class="number">1</span>;</span><br><span class="line">     <span class="comment">// 只有low小于等于high才进行循环</span></span><br><span class="line">     <span class="keyword">while</span> (low &lt;= high) &#123;</span><br><span class="line">         <span class="comment">// 折半算法，(low+high)/2缩小查找范围,按位运算比较快</span></span><br><span class="line">         <span class="comment">// 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) &gt;&gt; 1)</span></span><br><span class="line">         <span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span>(low + high) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">         <span class="comment">// 若查找的值大于折半的值，增大low的索引范围</span></span><br><span class="line">         <span class="keyword">if</span> (arr[mid] &lt; target) &#123;</span><br><span class="line">             low = mid + <span class="number">1</span>;</span><br><span class="line">         &#125; <span class="keyword">else</span> <span class="keyword">if</span> (arr[mid] &gt; target) &#123;</span><br><span class="line">             <span class="comment">// 若查找的值小于折半的值，缩小high的索引范围</span></span><br><span class="line">             high = mid -<span class="number">1</span>;</span><br><span class="line">         &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">             <span class="comment">// 若查找的值刚好等于折半的值，那就说明已经查找到了，直接返回即可</span></span><br><span class="line">             <span class="keyword">return</span> mid;</span><br><span class="line">         &#125;</span><br><span class="line">     &#125;</span><br><span class="line">     <span class="comment">// 若high大于low，表示两者早都相遇，查询无结果返回-1</span></span><br><span class="line">     <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line"> &#125;</span><br></pre></td></tr></table></figure>

<p>即便写起来不费一点力气，那我还是要解释一下：</p>
<p>low、high、mid都是指数组下标，其中low和high表示当前查找的区间范围，初始low=0， high=len-1，mid表示[low, high]的中间位置。</p>
<p>我们通过对比arr[mid]与target的大小，来更新接下来要查找的区间范围，直到找到或者区间缩小为0，就退出。</p>
<p>当然，最开始初学二分算法时候，初学3个容易出错的地方，大家需要注意一下：</p>
<ol>
<li><p>循环退出条件</p>
<p>注意是low&lt;=high，而不是low&lt;high。</p>
</li>
<li><p>mid的取值</p>
<p>实际上，mid=(low+high)/2这种写法是有问题的。</p>
<p>因为如果low和high比较大的话，两者之和就有可能会溢出。</p>
<p>改进的方法是将mid的计算方式写成low+(high-low)/2。</p>
<p>更进一步，如果要将性能优化到极致的话，我们可以将这里的除以2操作转化成位运算low+((high-low)&gt;&gt;1)。</p>
<p>因为相比除法运算来说，计算机处理位运算要快得多。</p>
</li>
<li><p>low和high的更新</p>
<p>​    low=mid+1，high=mid-1。注意这里的+1和-1，如果直接写成low=mid或者high=mid，就可能会发生死循环。</p>
<p>​    比如，当high=3，low=3时，如果arr[3]不等于value，就会导致一直循环不退出。</p>
</li>
</ol>
<h1 id="3-惊人的查找速度"><a href="#3-惊人的查找速度" class="headerlink" title="3.惊人的查找速度"></a>3.惊人的查找速度</h1><p>二分查找是一种非常高效的查找算法，高效到什么程度呢？我们来分析一下它的时间复杂度。</p>
<p>我们假设数据大小是n，每次查找后数据都会缩小为原来的一半，也就是会除以2。最坏情况下，直到查找区间被缩小为空，才停止。</p>
<p><img src="https://ltyeamin.github.io/imgs/2022/03/20220312171952.png"></p>
<p>可以看出来，这是一个等比数列。其中n/2k=1时，k的值就是总共缩小的次数。</p>
<p>而每一次缩小操作只涉及两个数据的大小比较，所以，经过了k次区间缩小操作，时间复杂度就是O(k)。</p>
<p>通过n/2k=1，我们可以求得k=log2n，所以时间复杂度就是O(logn)。</p>
<h1 id="4-递归实现"><a href="#4-递归实现" class="headerlink" title="4.递归实现"></a>4.递归实现</h1><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 二分查找的递归实现</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> arr     查找的数组</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> low     低位索引</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> high    高位索引</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> target  查找目标值</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">recursiveBinarySearch</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> low, <span class="type">int</span> high, <span class="type">int</span> target)</span> &#123;</span><br><span class="line">    <span class="comment">// 校验low和high的合法性，若区间查找完直接返回-1，表示无法查找目标结果</span></span><br><span class="line">    <span class="keyword">if</span> (low &gt; high) &#123;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 计算mid二分值</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span>  low + ((high - low) &gt;&gt; <span class="number">1</span>);</span><br><span class="line">    <span class="comment">// 若查找的值大于折半的值，增大low的索引范围，递归式调用处理</span></span><br><span class="line">    <span class="keyword">if</span> (arr[mid] &lt; target) &#123;</span><br><span class="line">        <span class="keyword">return</span> recursiveBinarySearch(arr,mid + <span class="number">1</span>, high, target);</span><br><span class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (arr[mid] &gt; target) &#123;</span><br><span class="line">        <span class="comment">// 若查找的值小于折半的值，缩小high的索引范围,递归式处理</span></span><br><span class="line">        <span class="keyword">return</span> recursiveBinarySearch(arr, low, mid - <span class="number">1</span>, target);</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="comment">// 若查找的值刚好等于折半的值，那就说明已经查找到了，直接返回即可</span></span><br><span class="line">        <span class="keyword">return</span> mid;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">    <span class="type">int</span>[] arr = &#123;<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>,<span class="number">4</span>,<span class="number">5</span>,<span class="number">6</span>&#125;;</span><br><span class="line">    System.out.println(simpleBinarySearch(arr,<span class="number">9</span>));</span><br><span class="line">    System.out.println(recursiveBinarySearch(arr,<span class="number">0</span>,arr.length - <span class="number">1</span>,<span class="number">3</span>));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="5-局限性"><a href="#5-局限性" class="headerlink" title="5.局限性"></a>5.局限性</h1><p>前面我们分析过，二分查找的时间复杂度是O(logn)，查找数据的效率非常高。</p>
<p>不过，并不是什么情况下都可以用二分查找，它的应用场景是有很大局限性的。</p>
<p>那什么情况下适合用二分查找，什么情况下不适合呢？</p>
<p><strong>首先，二分查找依赖的是顺序表结构，简单点说就是数组。</strong></p>
<p>那二分查找能否依赖其他数据结构呢？比如链表。答案是不可以的，主要原因是二分查找算法需要按照下标随机访问元素。</p>
<p>数组按照下标随机访问数据的时间复杂度是O(1)，而链表随机访问的时间复杂度是O(n)。</p>
<p>所以，如果数据使用链表存储，二分查找的时间复杂就会变得很高。</p>
<p>二分查找只能用在数据是通过顺序表来存储的数据结构上。如果你的数据是通过其他数据结构存储的，则无法应用二分查找。</p>
<p><strong>其次，二分查找针对的是有序数据。</strong></p>
<p>二分查找对这一点的要求比较苛刻，数据必须是有序的。如果数据没有序，我们需要先排序。</p>
<p>排序的时间复杂度最低是O(nlogn)。所以，如果我们针对的是一组静态的数据，没有频繁地插入、删除，我们可以进行一次排序，多次二分查找。这样排序的成本可被均摊，二分查找的边际成本就会比较低。</p>
<p>但是，如果我们的数据集合有频繁的插入和删除操作，要想用二分查找，要么每次插入、删除操作之后保证数据仍然有序，要么在每次二分查找之前都先进行排序。</p>
<p>针对这种动态数据集合，无论哪种方法，维护有序的成本都是很高的。</p>
<p>所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。</p>
<p>针对动态变化的数据集合，二分查找将不再适用。</p>
<p>那针对动态数据集合，如何在其中快速查找某个数据呢？别急，二叉树等其他数据结构会解决此问题。</p>
<p><strong>再次，数据量太小不适合二分查找。</strong></p>
<p>如果要处理的数据量很小，完全没有必要用二分查找，顺序遍历就足够了。</p>
<p>比如我们在一个大小为10的数组中查找一个元素，不管用二分查找还是顺序遍历，查找速度都差不多。</p>
<p>只有数据量比较大的时候，二分查找的优势才会比较明显。</p>
<p>不过，这里有一个例外。如果数据之间的比较操作非常耗时，不管数据量大小，我都推荐使用二分查找。</p>
<p>比如，数组中存储的都是长度超过300的字符串，如此长的两个字符串之间比对大小，就会非常耗时。</p>
<p>我们需要尽可能地减少比较次数，而比较次数的减少会大大提高性能，这个时候二分查找就比顺序遍历更有优势。</p>
<p><strong>最后，数据量太大也不适合二分查找。</strong></p>
<p>二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。</p>
<p>比如，我们有1GB大小的数据，如果希望用数组来存储，那就需要1GB的连续内存空间。</p>
<p>注意这里的“连续”二字，也就是说，即便有2GB的内存空间剩余，但是如果这剩余的2GB内存空间都是零散的，没有连续的1GB大小的内存空间，那照样无法申请一个1GB大小的数组。</p>
<p>而我们的二分查找是作用在数组这种数据结构之上的，所以太大的数据用数组存储就比较吃力了，也就不能用二分查找了。</p>
<h1 id="6-不知所措的变体"><a href="#6-不知所措的变体" class="headerlink" title="6.不知所措的变体"></a>6.不知所措的变体</h1><p>上述讲的二分查找都是基于数组有序<strong>且不重复</strong>元素处理的。所以大家都觉得二分查找算法很简单。</p>
<p>若考虑重复元素，那么仔细思考如下图片的问题，你还会觉得二分查找算法简单吗？</p>
<p><img src="https://ltyeamin.github.io/imgs/2022/03/20220312174215.png"></p>
<h2 id="6-1-变体一：查找第一个值等于给定的元素"><a href="#6-1-变体一：查找第一个值等于给定的元素" class="headerlink" title="6.1 变体一：查找第一个值等于给定的元素"></a>6.1 变体一：查找第一个值等于给定的元素</h2><p>下面有这样一个有序数组，其中，a[5]，a[6]，a[7]的值都等于8，是重复的数据。</p>
<p>我们希望查找第一个等于8的数据，也就是下标是5的元素。</p>
<p><img src="https://ltyeamin.github.io/imgs/2022/03/20220313165114.png"></p>
<p>如果我们之前二分查找的代码实现，首先拿8与区间的中间值a[4]比较，8比6大，于是在下标5到9之间继续查找。</p>
<p>下标5和9的中间位置是下标7，a[7]正好等于8，所以代码就返回了。</p>
<p>尽管a[7]也等于8，但它并不是我们想要找的第一个等于8的元素，因为第一个值等于8的元素是数组下标为5的元素。</p>
<p>那么我们之前讲的二分查找代码就无法处理这种情况了。</p>
<p>所以，针对这个变形问题，我们可以稍微改造一下就可以了。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 二分查找：查找第一个值等于给定值的元素</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> arr    查找数组</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> target 查找指定的值</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span>       返回查找值的数组索引，返回-1表示查询无结果</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">findFirstBinarySearch</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> target)</span> &#123;</span><br><span class="line">    <span class="comment">// 获取数组长度</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">len</span> <span class="operator">=</span> arr.length;</span><br><span class="line">    <span class="comment">// 校验数组</span></span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">null</span> ||  len == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">low</span> <span class="operator">=</span> <span class="number">0</span>, high = len - <span class="number">1</span>;</span><br><span class="line">    <span class="comment">// 只有low小于等于high才进行循环</span></span><br><span class="line">    <span class="keyword">while</span> (low &lt;= high) &#123;</span><br><span class="line">        <span class="comment">// 折半算法，(low+high)/2缩小查找范围,按位运算比较快</span></span><br><span class="line">        <span class="comment">// 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) &gt;&gt; 1)</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span>(low + high) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">        <span class="comment">// 若查找的值大于折半的值，增大low的索引范围</span></span><br><span class="line">        <span class="keyword">if</span> (arr[mid] &lt; target) &#123;</span><br><span class="line">            low = mid + <span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (arr[mid] &gt; target) &#123;</span><br><span class="line">            <span class="comment">// 若查找的值小于折半的值，缩小high的索引范围</span></span><br><span class="line">            high = mid -<span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// 这里稍微改一下即可，当mid == 0，表示target的索引就是数组第一个，则直接返回即可</span></span><br><span class="line">            <span class="comment">// 若mid != 0，并且arr[mid - 1]不等于target，则表示没有重复的了，也可以直接返回</span></span><br><span class="line">            <span class="keyword">if</span> ( mid == <span class="number">0</span> || arr[mid - <span class="number">1</span>] != target) &#123;</span><br><span class="line">                <span class="keyword">return</span> mid;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 若arr[mid - 1]也是等于target，那说明我们此时查找的mid肯定不是最优解，那我们需要更新high的值继续查找。</span></span><br><span class="line">            <span class="comment">// 因为我们查找的元素肯定出现在[low, mid-1]之间。</span></span><br><span class="line">            high = mid - <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 若high大于low，表示两者早都相遇，查询无结果返回-1</span></span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="6-2-变体二：查找最后一个值等于给定值的元素"><a href="#6-2-变体二：查找最后一个值等于给定值的元素" class="headerlink" title="6.2 变体二：查找最后一个值等于给定值的元素"></a>6.2 变体二：查找最后一个值等于给定值的元素</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 二分查找：查找最后一个值等于给定值的元素</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> arr    查找数组</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> target 查找指定的值</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span>       返回查找值的数组索引，返回-1表示查询无结果</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">findLastBinarySearch</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> target)</span> &#123;</span><br><span class="line">    <span class="comment">// 获取数组长度</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">len</span> <span class="operator">=</span> arr.length;</span><br><span class="line">    <span class="comment">// 校验数组</span></span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">null</span> ||  len == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">low</span> <span class="operator">=</span> <span class="number">0</span>, high = len - <span class="number">1</span>;</span><br><span class="line">    <span class="comment">// 只有low小于等于high才进行循环</span></span><br><span class="line">    <span class="keyword">while</span> (low &lt;= high) &#123;</span><br><span class="line">        <span class="comment">// 折半算法，(low+high)/2缩小查找范围,按位运算比较快</span></span><br><span class="line">        <span class="comment">// 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) &gt;&gt; 1)</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span>(low + high) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">        <span class="comment">// 若查找的值大于折半的值，增大low的索引范围</span></span><br><span class="line">        <span class="keyword">if</span> (arr[mid] &lt; target) &#123;</span><br><span class="line">            low = mid + <span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (arr[mid] &gt; target) &#123;</span><br><span class="line">            <span class="comment">// 若查找的值小于折半的值，缩小high的索引范围</span></span><br><span class="line">            high = mid -<span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="comment">// 这里稍微改一下即可，当mid为数组最后一个元素时,那么就是我们要找的值,直接返回即可</span></span><br><span class="line">            <span class="comment">// 若mid不是数组最后1个元素时，并且arr[mid + 1]不等于target，则表示就是我们查找的最后1个值，也可以直接返回</span></span><br><span class="line">            <span class="keyword">if</span> ( mid == len - <span class="number">1</span> || arr[mid + <span class="number">1</span>] != target) &#123;</span><br><span class="line">                <span class="keyword">return</span> mid;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 若arr[mid + 1]也是等于target，那说明我们此时查找的mid肯定不是最优解，那我们需要更新low的值继续查找。</span></span><br><span class="line">            <span class="comment">// 因为我们查找的元素肯定出现在[low, mid-1]之间。</span></span><br><span class="line">            low = mid + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 若high大于low，表示两者早都相遇，查询无结果返回-1</span></span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>如果arr[mid]这个元素已经是数组中的最后一个元素了，那它肯定是我们要找的；</p>
<p>如果arr[mid]的后一个元素a[mid+1]不等于target，那也说明a[mid]就是我们要找的最后一个值等于给定值的元素。</p>
<p>如果我们经过检查之后，发现a[mid]后面的一个元素arr[mid+1]也等于target，那说明当前的这个arr[mid]并不是最后一个值等于给定值的元素。</p>
<p>我们就更新low=mid+1，因为要找的元素肯定出现在[mid+1, high]之间。</p>
<h2 id="6-3-变体三：查找第一个大于等于给定值的元素"><a href="#6-3-变体三：查找第一个大于等于给定值的元素" class="headerlink" title="6.3 变体三：查找第一个大于等于给定值的元素"></a>6.3 变体三：查找第一个大于等于给定值的元素</h2><p>现在我们再来看另外一类变形问题。在有序数组中，查找第一个大于等于给定值的元素。</p>
<p>比如，数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于5的元素，那就是6。</p>
<p>实际上，实现的思路跟前面的那两种变形问题的实现思路类似，代码写起来甚至更简洁。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">    * 二分查找：查找第一个大于等于给定值的元素</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@param</span> arr    查找数组</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@param</span> target 查找指定的值</span></span><br><span class="line"><span class="comment">    * <span class="doctag">@return</span>       返回查找值的数组索引，返回-1表示查询无结果</span></span><br><span class="line"><span class="comment">    */</span></span><br><span class="line">   <span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">findFirstGtBinarySearch</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> target)</span> &#123;</span><br><span class="line">       <span class="comment">// 获取数组长度</span></span><br><span class="line">       <span class="type">int</span> <span class="variable">len</span> <span class="operator">=</span> arr.length;</span><br><span class="line">       <span class="comment">// 校验数组</span></span><br><span class="line">       <span class="keyword">if</span> (arr == <span class="literal">null</span> ||  len == <span class="number">0</span>) &#123;</span><br><span class="line">           <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">       &#125;</span><br><span class="line">       <span class="comment">// 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引</span></span><br><span class="line">       <span class="type">int</span> <span class="variable">low</span> <span class="operator">=</span> <span class="number">0</span>, high = len - <span class="number">1</span>;</span><br><span class="line">       <span class="comment">// 只有low小于等于high才进行循环</span></span><br><span class="line">       <span class="keyword">while</span> (low &lt;= high) &#123;</span><br><span class="line">           <span class="comment">// 折半算法，(low+high)/2缩小查找范围,按位运算比较快</span></span><br><span class="line">           <span class="comment">// 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) &gt;&gt; 1)</span></span><br><span class="line">           <span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span>  low + ((high - low) &gt;&gt; <span class="number">1</span>);</span><br><span class="line">           <span class="comment">// 若查找的值大于折半的值，增大low的索引范围</span></span><br><span class="line">           <span class="keyword">if</span> (arr[mid] &lt; target) &#123;</span><br><span class="line">               low = mid + <span class="number">1</span>;</span><br><span class="line">           &#125; <span class="keyword">else</span> <span class="keyword">if</span> (arr[mid] &gt;= target) &#123;</span><br><span class="line">               <span class="comment">// arr[mid] &gt; target 只有这种方式才会处理</span></span><br><span class="line">               <span class="keyword">if</span> ( mid == <span class="number">0</span> || arr[mid - <span class="number">1</span>] &lt; target) &#123;</span><br><span class="line">                   <span class="keyword">return</span> mid;</span><br><span class="line">               &#125;</span><br><span class="line">               high = mid - <span class="number">1</span>;</span><br><span class="line">           &#125;</span><br><span class="line">       &#125;</span><br><span class="line">       <span class="comment">// 若high大于low，表示两者早都相遇，查询无结果返回-1</span></span><br><span class="line">       <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">   &#125;</span><br></pre></td></tr></table></figure>

<h2 id="6-4-变体四：查找最后一个小于等于给定值的元素"><a href="#6-4-变体四：查找最后一个小于等于给定值的元素" class="headerlink" title="6.4 变体四：查找最后一个小于等于给定值的元素"></a>6.4 变体四：查找最后一个小于等于给定值的元素</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 二分查找：查找最后一个小于等于给定值的元素</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> arr    查找数组</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> target 查找指定的值</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span>       返回查找值的数组索引，返回-1表示查询无结果</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">findLastLtBinarySearch</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> target)</span> &#123;</span><br><span class="line">    <span class="comment">// 获取数组长度</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">len</span> <span class="operator">=</span> arr.length;</span><br><span class="line">    <span class="comment">// 校验数组</span></span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">null</span> ||  len == <span class="number">0</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 定义low、high、mid变量，low初始化为数组起始索引，high初始化为数组末尾索引</span></span><br><span class="line">    <span class="type">int</span> <span class="variable">low</span> <span class="operator">=</span> <span class="number">0</span>, high = len - <span class="number">1</span>;</span><br><span class="line">    <span class="comment">// 只有low小于等于high才进行循环</span></span><br><span class="line">    <span class="keyword">while</span> (low &lt;= high) &#123;</span><br><span class="line">        <span class="comment">// 折半算法，(low+high)/2缩小查找范围,按位运算比较快</span></span><br><span class="line">        <span class="comment">// 当数组元素巨多时，这块代码可能溢出，可以优化为mid =low + ((high - low) &gt;&gt; 1)</span></span><br><span class="line">        <span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span>  low + ((high - low) &gt;&gt; <span class="number">1</span>);</span><br><span class="line">        <span class="comment">// 若查找的值大于折半的值，增大low的索引范围</span></span><br><span class="line">        <span class="keyword">if</span> (arr[mid] &lt;= target) &#123;</span><br><span class="line">            <span class="keyword">if</span> ( mid == len-<span class="number">1</span> || arr[mid + <span class="number">1</span>] &gt; target) &#123;</span><br><span class="line">                <span class="keyword">return</span> mid;</span><br><span class="line">            &#125;</span><br><span class="line">            low = mid + <span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            high = mid - <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 若high大于low，表示两者早都相遇，查询无结果返回-1</span></span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></section>
    <!-- Tags START -->
    
      <div class="tags">
        <span>Tags:</span>
        
  <a href="/tags#算法" >
    <span class="tag-code">算法</span>
  </a>

      </div>
    
    <!-- Tags END -->
    <!-- NAV START -->
    
  <div class="nav-container">
    <!-- reverse left and right to put prev and next in a more logic postition -->
    
      <a class="nav-left" href="/2022/01/06/%E6%94%AF%E4%BB%98%E9%87%8D%E6%9E%84%E4%B9%8B%E8%B7%AF/">
        <span class="nav-arrow">← </span>
        
          支付重构之路
        
      </a>
    
    
      <a class="nav-right" href="/2022/05/02/%E3%80%90%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E3%80%91%E9%AB%98%E6%95%88%E7%9A%84%E4%BD%8D%E8%BF%90%E7%AE%97/">
        
          【数据结构与算法】高效的位运算
        
        <span class="nav-arrow"> →</span>
      </a>
    
  </div>

    <!-- NAV END -->
    <!-- 打赏 START -->
    
      <div class="money-like">
        <div class="reward-btn">
          赏
          <span class="money-code">
            <span class="alipay-code">
              <div class="code-image"></div>
              <b>使用支付宝打赏</b>
            </span>
            <span class="wechat-code">
              <div class="code-image"></div>
              <b>使用微信打赏</b>
            </span>
          </span>
        </div>
        <p class="notice">若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏</p>
      </div>
    
    <!-- 打赏 END -->
    <!-- 二维码 START -->
    
      <div class="qrcode">
        <canvas id="share-qrcode"></canvas>
        <p class="notice">扫描二维码，分享此文章</p>
      </div>
    
    <!-- 二维码 END -->
    
      <!-- Utterances START -->
      <div id="utterances"></div>
      <script src="https://utteranc.es/client.js"
        repo="ltyeamin/blogtalks"
        issue-term="pathname"
        theme="github-light"
        crossorigin="anonymous"
        async></script>    
      <!-- Utterances END -->
    
  </article>
  <!-- Article END -->
  <!-- Catalog START -->
  
    <aside class="catalog-container">
  <div class="toc-main">
    <strong class="toc-title">Catalog</strong>
    
      <ol class="toc-nav"><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#1-%E5%89%8D%E8%A8%80"><span class="toc-nav-text">1.前言</span></a></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#2-%E4%B8%8D%E5%85%A5%E7%9C%BC%E7%9A%84%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE"><span class="toc-nav-text">2. 不入眼的二分查找</span></a></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#3-%E6%83%8A%E4%BA%BA%E7%9A%84%E6%9F%A5%E6%89%BE%E9%80%9F%E5%BA%A6"><span class="toc-nav-text">3.惊人的查找速度</span></a></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#4-%E9%80%92%E5%BD%92%E5%AE%9E%E7%8E%B0"><span class="toc-nav-text">4.递归实现</span></a></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#5-%E5%B1%80%E9%99%90%E6%80%A7"><span class="toc-nav-text">5.局限性</span></a></li><li class="toc-nav-item toc-nav-level-1"><a class="toc-nav-link" href="#6-%E4%B8%8D%E7%9F%A5%E6%89%80%E6%8E%AA%E7%9A%84%E5%8F%98%E4%BD%93"><span class="toc-nav-text">6.不知所措的变体</span></a><ol class="toc-nav-child"><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#6-1-%E5%8F%98%E4%BD%93%E4%B8%80%EF%BC%9A%E6%9F%A5%E6%89%BE%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%80%BC%E7%AD%89%E4%BA%8E%E7%BB%99%E5%AE%9A%E7%9A%84%E5%85%83%E7%B4%A0"><span class="toc-nav-text">6.1 变体一：查找第一个值等于给定的元素</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#6-2-%E5%8F%98%E4%BD%93%E4%BA%8C%EF%BC%9A%E6%9F%A5%E6%89%BE%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E5%80%BC%E7%AD%89%E4%BA%8E%E7%BB%99%E5%AE%9A%E5%80%BC%E7%9A%84%E5%85%83%E7%B4%A0"><span class="toc-nav-text">6.2 变体二：查找最后一个值等于给定值的元素</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#6-3-%E5%8F%98%E4%BD%93%E4%B8%89%EF%BC%9A%E6%9F%A5%E6%89%BE%E7%AC%AC%E4%B8%80%E4%B8%AA%E5%A4%A7%E4%BA%8E%E7%AD%89%E4%BA%8E%E7%BB%99%E5%AE%9A%E5%80%BC%E7%9A%84%E5%85%83%E7%B4%A0"><span class="toc-nav-text">6.3 变体三：查找第一个大于等于给定值的元素</span></a></li><li class="toc-nav-item toc-nav-level-2"><a class="toc-nav-link" href="#6-4-%E5%8F%98%E4%BD%93%E5%9B%9B%EF%BC%9A%E6%9F%A5%E6%89%BE%E6%9C%80%E5%90%8E%E4%B8%80%E4%B8%AA%E5%B0%8F%E4%BA%8E%E7%AD%89%E4%BA%8E%E7%BB%99%E5%AE%9A%E5%80%BC%E7%9A%84%E5%85%83%E7%B4%A0"><span class="toc-nav-text">6.4 变体四：查找最后一个小于等于给定值的元素</span></a></li></ol></li></ol>
    
  </div>
</aside>
  
  <!-- Catalog END -->
</main>

<script>
  (function () {
    var url = 'http://example.com/2022/01/23/【数据结构与算法】不知所措的二分查找/';
    var banner = ''
    if (banner !== '' && banner !== 'undefined' && banner !== 'null') {
      $('#article-banner').css({
        'background-image': 'url(' + banner + ')'
      })
    } else {
      $('#article-banner').geopattern(url)
    }
    $('.header').removeClass('fixed-header')

    // error image
    $(".markdown-content img").on('error', function() {
      $(this).attr('src', '/css/images/error_icon.png')
      $(this).css({
        'cursor': 'default'
      })
    })

    // zoom image
    $(".markdown-content img").on('click', function() {
      var src = $(this).attr('src')
      if (src !== '/css/images/error_icon.png') {
        var imageW = $(this).width()
        var imageH = $(this).height()

        var zoom = ($(window).width() * 0.95 / imageW).toFixed(2)
        zoom = zoom < 1 ? 1 : zoom
        zoom = zoom > 2 ? 2 : zoom
        var transY = (($(window).height() - imageH) / 2).toFixed(2)

        $('body').append('<div class="image-view-wrap"><div class="image-view-inner"><img src="'+ src +'" /></div></div>')
        $('.image-view-wrap').addClass('wrap-active')
        $('.image-view-wrap img').css({
          'width': `${imageW}`,
          'transform': `translate3d(0, ${transY}px, 0) scale3d(${zoom}, ${zoom}, 1)`
        })
        $('html').css('overflow', 'hidden')

        $('.image-view-wrap').on('click', function() {
          $(this).remove()
          $('html').attr('style', '')
        })
      }
    })
  })();
</script>


  <script>
    var qr = new QRious({
      element: document.getElementById('share-qrcode'),
      value: document.location.href
    });
  </script>






    <div class="scroll-top">
  <span class="arrow-icon"></span>
</div>
    <footer class="app-footer">
  <p class="copyright">
    &copy; 2024 | Proudly powered by <a href="https://hexo.io" target="_blank">Hexo</a>
    <br>
    Theme by <a target="_blank" rel="noopener" href="https://github.com/ltyeamin">tong.li</a>
  </p>
</footer>

<script>
  function async(u, c) {
    var d = document, t = 'script',
      o = d.createElement(t),
      s = d.getElementsByTagName(t)[0];
    o.src = u;
    if (c) { o.addEventListener('load', function (e) { c(null, e); }, false); }
    s.parentNode.insertBefore(o, s);
  }
</script>
<script>
  async("https://cdn.staticfile.org/fastclick/1.0.6/fastclick.min.js", function(){
    FastClick.attach(document.body);
  })
</script>

<script>
  var hasLine = 'true';
  async("https://cdn.staticfile.org/highlight.js/9.12.0/highlight.min.js", function(){
    $('figure pre').each(function(i, block) {
      var figure = $(this).parents('figure');
      if (hasLine === 'false') {
        figure.find('.gutter').hide();
      }
      hljs.configure({useBR: true});
      var lang = figure.attr('class').split(' ')[1] || 'code';
      var codeHtml = $(this).html();
      var codeTag = document.createElement('code');
      codeTag.className = lang;
      codeTag.innerHTML = codeHtml;
      $(this).attr('class', '').empty().html(codeTag);
      figure.attr('data-lang', lang.toUpperCase());
      hljs.highlightBlock(block);
    });
  })
</script>
<!-- Baidu Tongji -->



<script src='https://cdn.staticfile.org/mermaid/8.11.2/mermaid.min.js'></script>



<script src="/js/script.js"></script>


  </body>
</html>